package ArrayList;

//自己实现一个简单的顺序表
//直接以 int 为例就行了 ， 就不写泛型了
public class MyArrayList {
    //真正存储数据 ， 顺序表本身就是基于数组的封装
    private  int[] arr;
    //约定 arr 中的前 size 个元素 ， 表示有效元素
    //加入 arr 的 new int[10] ，但是size任然是 0 ，那么ArrayList 也视为是一个空盒子
    //后续 add 添加几个元素就 size+加几个元素 ， size 为几就认为有效元素是几个
    //[0,size) 就是整个 arr 中有效元素的部分 ， [size,arr.length)就是无效元素的区间
    //删除一个元素，其实就是把这个文件标记为无效 ， 其实文件任然在数组中
    //删除逻辑：通过标记，表示那部分有效那部分无效
    private int size = 0;
    /////////////////////////////////////////////////////////////////
    //MyArrayList 的正式代码
    /////////////////////////////////////////////////////////////////

    //构造方法
    public MyArrayList(){
        //无参版本默认容量 10
        arr = new int[10];
    }
    public MyArrayList(int capacity) {
        //只是创建了一个有容量的空间 ， 这些空间上的元素都是无效的 ， 通过 add 添加有效元素
        arr = new int[capacity];//指定容量
    }

    //获取元素个数
    public int size() {
        return size;
    }

    //新增元素 ， 尾插
    public void add(int val) {
        //把当前新的元素放到最后一个位置上 ， 下标为 size 的位置 [0,size)区间
        if(size == arr.length){
            //数组满了，需要进行扩容
            resize();
        }
        arr[size] = val;
        size++;
    }

    //一般不能给用户接触的我们要用 private
    private void resize(){
        //1.先创建一个更长的数组
        //                    arr.length + (arr.length>>1)
        int[] newArr = new int[(int)(arr.length*1.5)];//得到一个double 需要强制类型转换
        //2.把原来的数组元素复制到新数组上
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        //用新的数组替代旧的数组
        //旧的数组就会被垃圾回收机制给释放
        arr = newArr;
    }

    //任意位置插入元素
    public void add(int index,int val){
        //把 index 的位置及其以后的元素都给往后一次挪一步 ，注意要从后往前挪
        //具体搬运的次数取决于 i 的位置
        //i 越靠前 ， 搬运的次数就越多 时间复杂度O(N)
        //尾插时间复杂度为 O(1) , 但是尾插一旦涉及到扩容就会触发搬运数组 ， 此时时间复杂的就是O(N) , 但是通常认为尾插都是O（1）
        if(index < 0 ||index > size){//判断传入的 index 是否合法
            throw new IndexOutOfBoundsException("Index out of Bounds!");
        }
        //如果数组满了 ， 继续添加一个元素 ， 也要扩容
        if(size == arr.length){
            //扩容
            resize();
        }
        //搬运元素 ， 从后往前一次把每个元素都搬运一个位置
        for (int i = size; i >= index; i--) {//
            arr[i+1] = arr[i];//腾出 index 位置
        }
        //把新元素放入到 index 位置
        arr[index] = val;
        //更新 size
        size++;
    }

    //根据下标获取元素
    public void get(int index){

    }

    //根据下标设置元素
    public void set(int index,int val){

    }

    //删除元素 , 按照下标来删除
    public int remove(int index){
        return 0;
    }

    //删除元素 , 按照值来删除
    public void delete(int val){

    }

    //判断元素是否存在
    public boolean contains (int val) {
        return false;
    }

    //查找元素所在的位置
    public int indexOf(int val) {
        return 0;
    }

    //
    public int lastIndexOf(int val){
        return 0;
    }

    //清除
    public void clear() {

    }

    //打印操作 ， 用 toString ， 把 MyArrayList 转化为字符串
    @Override //重写父类的 toString ，实现自己的 toString 方法
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(arr[i]);
            if (i<size){
//                System.out.println(",");
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
    //////////////////////////////////////////////////////////////////////////////////////////
    //下面是一些测试方法
    /////////////////////////////////////////////////////////////////////////////////////////
    private static void test1(){
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        list.add(11);
        list.add(12);
        list.add(13);
        System.out.println(list.size());
        System.out.println(list.toString());
    }
    private static void test2(){
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2,200);
        System.out.println(list.toString());

    }
    public static void main(String[] args) {
        test2();
    }
}
